package com.awei.study.dataStructure.tree;

import com.awei.study.dataStructure.queue.ArrayQueue_DoubleEnd;
import com.awei.study.dataStructure.queue.LinkQueue;
import com.awei.study.dataStructure.queue.LinkQueue_DoubleEnd;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liweilong
 * @Date 2023/5/24 9:22
 */
public class Btree<E> {
    static class TreeNode<E> {
        E value;

        TreeNode<E> left;
        TreeNode<E> right;

        public TreeNode(TreeNode<E> left, E value, TreeNode<E> right) {
            this.left = left;
            this.value = value;
            this.right = right;
        }
    }

    @Test
    public void test_btree() {
        TreeNode<Integer> treeNode = new TreeNode<>(
                new TreeNode<Integer>(
                        new TreeNode<Integer>(null,4, null),
                        2,
                        new TreeNode<Integer>(null,5, null)
                ),
                1,
                new TreeNode<Integer>(
                        new TreeNode<Integer>(null,6, null),
                        3,
                        new TreeNode<Integer>(null,7, null)
                )
        );
        List<List<Integer>> list = new ArrayList<>();
        LinkQueue<TreeNode<Integer>> queue = new LinkQueue<>();
        queue.offer(treeNode);
        int nxtSize = 1;
        while(!queue.isEmpty()) {
            int size = 0;
            List<Integer> newList = new ArrayList<>();
            for (int i = 0; i < nxtSize; i++) {
                TreeNode<Integer> first = queue.poll();
                newList.add(first.value);
                System.out.print(first.value + " ");
                if(first.left != null) {
                    TreeNode<Integer> left = first.left;
                    queue.offer(left);
                    size++;
                }
                if(first.right != null) {
                    TreeNode<Integer> right = first.right;
                    queue.offer(right);
                    size++;
                }
            }
            list.add(newList);
            nxtSize = size;
            System.out.println();
        }
        System.out.println(list);
    }

    @Test
    public void test_z_btree() {
        TreeNode<Integer> treeNode = new TreeNode<>(
                new TreeNode<Integer>(
                        new TreeNode<Integer>(null,4, null),
                        2,
                        new TreeNode<Integer>(null,5, null)
                ),
                1,
                new TreeNode<Integer>(
                        new TreeNode<Integer>(null,6, null),
                        3,
                        new TreeNode<Integer>(null,7, null)
                )
        );
//        List<ArrayQueue_DoubleEnd<Integer>> list = new ArrayList<>();
        List<LinkQueue_DoubleEnd<Integer>> list = new ArrayList<>();
        LinkQueue<TreeNode<Integer>> queue = new LinkQueue<>();
        queue.offer(treeNode);
        int nxtSize = 1;
        boolean isSingle = true;
        while(!queue.isEmpty()) {
            int size = 0;
//            ArrayQueue_DoubleEnd<Integer> newList = new ArrayQueue_DoubleEnd<Integer>(nxtSize);
            LinkQueue_DoubleEnd<Integer> newList = new LinkQueue_DoubleEnd<Integer>(nxtSize);
            for (int i = 0; i < nxtSize; i++) {
                TreeNode<Integer> first = queue.poll();
//                newList.add(first.value);
                if(isSingle) {
                    newList.offerTail(first.value);
                }else {
                    newList.offerHead(first.value);
                }
                System.out.print(first.value + " ");
                if(first.left != null) {
                    TreeNode<Integer> left = first.left;
                    queue.offer(left);
                    size++;
                }
                if(first.right != null) {
                    TreeNode<Integer> right = first.right;
                    queue.offer(right);
                    size++;
                }
            }
            isSingle = !isSingle;
            list.add(newList);
            nxtSize = size;
            System.out.println();
        }
//        System.out.println(list);
//        for (ArrayQueue_DoubleEnd<Integer> integers : list) {
        for (LinkQueue_DoubleEnd<Integer> integers : list) {
            for (Integer integer : integers) {
                System.out.print(integer);
            }
            System.out.println();
        }
    }
}
